#ifndef SetSolver_h
#define SetSolver_h

#include "SetSolverSquareSet.h"
#include <iostream>
#include <memory>
#include <string>

using std::string;
using std::vector;
// do not add additional libraries

class SetSolver {
private:
    int boardSize = 9;
    vector<vector<SetSolverSquareSet>> board;

public:
    SetSolver() {
        board = vector<vector<SetSolverSquareSet>>(
                boardSize, vector<SetSolverSquareSet>(boardSize));
    }

    void PopulateBoard(vector<string> skeletonBoard) {
        for (int i = 0; i < boardSize; ++i) {
            for (int j = 0, k = 0; j < skeletonBoard[i].length(); ++j, ++k) {
                if (skeletonBoard[i][j] != '*') {
                    char ch = skeletonBoard[i][j];
                    if (ch == '-') {
                        int num = skeletonBoard[i][++j] - '0';
                        board[i][k].set.push_back(num * -1);
                    } else {
                        int num = ch - '0';
                        board[i][k].set.push_back(num);
                    }
                } else {
                    board[i][k].set.push_back(99);
                }
            }
        }
    }

    int ReturnValue(size_t row, size_t col) {
        if (!board[row][col].set.empty()) {
            return board[row][col].set[0];
        }

        // return the right value
        return 0; // This line was added temporarily
    }

    void Solve() {
        backtrack(0, 0);
    }

    bool backtrack(int row, int col) {
        if (col == boardSize) {
            return backtrack(row + 1, 0);
        }

        if (row == boardSize) {
            return true;
        }

        for (int i = row; i < boardSize; ++i) {
            for (int j = col; j < boardSize; ++j) {
                if (board[row][col].set[0] != 99) {
                    return backtrack(row, col + 1);
                }

                for (int num = 1; num <= 9; num++) {
                    board[row][col].set[0] = num;
                    if (!isValid(row, col, num)) {
                        continue;
                    }

                    if (backtrack(row, col + 1)) {
                        return true;
                    }
                    board[row][col].set[0] = 99;
                }
                return false;
            }
        }
        return false;
    }

    bool isValid(int row, int col, int num) {
        vector<int> rowSet, colSet;
        bool startRow = false, startCol = false;

        for (int i = 0; i < boardSize; ++i) {
            if (i != col && board[row][i].set[0] == num) {
                return false;
            }

            if (i != row && board[i][col].set[0] == num) {
                return false;
            }

            if (i < boardSize - 1 && board[row][i].set[0] == 0 && !startRow &&
                board[row][i + 1].set[0] != 0) {
                startRow = true;
                i++;
            }

            if (startRow) {
                if (board[row][i].set[0] == 0) {
                    startRow = false;
                    if (!check(rowSet)) {
                        return false;
                    }
                } else if (board[row][i].set[0] != 99) {
                    int n = board[row][i].set[0];
                    if (n < 0) {
                        n *= -1;
                    }
                    rowSet.push_back(n);
                }
            }

            if (i < boardSize - 1 && board[i][col].set[0] == 0 && !startCol &&
                board[i + 1][col].set[0] != 0) {
                startCol = true;
                i++;
            }

            if (startCol) {
                if (board[i][col].set[0] == 0) {
                    startCol = false;
                    if (!check(colSet)) {
                        return false;
                    }
                } else if (board[i][col].set[0] != 99) {
                    int n = board[i][col].set[0];
                    if (n < 0) {
                        n *= -1;
                    }
                    colSet.push_back(n);
                }
            }
        }

        return true;
    }

private:
    void printBoard() {
        for (int i = 0; i < boardSize; ++i) {
            for (int j = 0; j < boardSize; ++j) {
                if (!board[i][j].set.empty())
                    std::cout << board[i][j].set[0] << " ";
                else
                    std::cout << "* ";
            }
            std::cout << std::endl;
        }
    }

    bool check(vector<int> &vec) {
        if (vec.size() > 1) {
            sortVector(vec);
            for (int i = 0; i < vec.size() - 1; ++i) {
                if (vec[i + 1] - vec[i] != 1) {
                    return false;
                }
            }
        }

        return true;
    }

    void sortVector(vector<int> &vec) {
        for (int i = 0; i < vec.size(); ++i) {
            for (int j = i + 1; j < vec.size(); ++j) {
                if (vec[i] > vec[j]) {
                    int temp = vec[i];
                    vec[i] = vec[j];
                    vec[j] = temp;
                }
            }
        }
    }
};

#endif /* SetSolver_h */
